package binaryTree;

import java.util.Stack;

public class InOrder {
	public static void inOrder(TreeNode root) {
		if(root!=null) {
			Stack<TreeNode> s=new Stack<>();
			//只要栈不为空或者root不为空，就不停止
			while(!s.isEmpty()||root!=null) {
				//只要节点root存在左孩子，就一直遍历左孩子
				if(root!=null) {
					s.push(root);     //遍历过程加入栈中
					root=root.left;   //到下一个左孩子
				}
				//如果root为空，即此时左孩子为空，则处理中间节点对头
				else {
					TreeNode cur=s.pop();  //队头出队
					System.out.print(cur.val+" ");
					root=cur.right;        //处理右孩子，右孩子重复左孩子的逻辑
				}
			}
		}
	}
}
